import java.util.*;

/**
 * Created by zhourh on 2018/6/8.
 * 给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。

 （注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）

 位运算
 */
public class PrimeNumber0fSetBitsInBinaryRepresentation {

    public static final List<Integer> primes = Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31);

    public static final Map<Integer, Integer> hammingWeights = new HashMap();

    public static void main(String[] args) {
        System.out.println("6 -> 10 count of prime = " + new PrimeNumber0fSetBitsInBinaryRepresentation().countPrimeSetBits(6, 10));
        System.out.println("10 -> 15 count of prime = " + new PrimeNumber0fSetBitsInBinaryRepresentation().countPrimeSetBits(10, 15));
    }

    public int countPrimeSetBits(int L, int R) {
        int result = 0;
        for (int i = L; i <= R; i++) {
            int weight = hammingWeights.containsKey(i) ? hammingWeights.get(i) : Integer.bitCount(i);
            if (!hammingWeights.containsKey(i)) {
                hammingWeights.put(i, weight);
            }

            result += primes.contains(weight) ? 1 : 0;
        }

        return result;
    }

    public int hammingWeight(int n) {
        int mask = 0x0001;
        int weight = 0;
        while (mask != 0) {
            weight += ((n & mask) != 0 ? 1 : 0);
            mask <<= 1;
        }

        return weight;
    }
}

